/**
 * 剑指 Offer 49. 丑数
 * https://leetcode-cn.com/problems/chou-shu-lcof/
 */

/**
 * @param {number} n
 * @return {number}
 */
function nthUglyNumber(n) {
  const dp = new Array(n + 1);
  dp[1] = 1;
  let index2 = 1;
  let index3 = 1;
  let index5 = 1;
  for (let i = 2; i <= n; i += 1) {
    const value2 = dp[index2] * 2;
    const value3 = dp[index3] * 3;
    const value5 = dp[index5] * 5;
    const value = Math.min(value2, value3, value5);
    dp[i] = value;
    if (value === value2) {
      index2 += 1;
    }
    if (value === value3) {
      index3 += 1;
    }
    if (value === value5) {
      index5 += 1;
    }
  }
  return dp[n];
}

console.log(nthUglyNumber(1) === 1);
console.log(nthUglyNumber(6) === 6);
console.log(nthUglyNumber(7) === 8);
console.log(nthUglyNumber(10) === 12);
console.log(nthUglyNumber(100) === 1536);
console.log(nthUglyNumber(1690) === 2123366400);
